Lecture 10

Agenda for this lecture

• Overview and motivating example: Game of Life
• Application areas
• Definition and properties
• Classification
• Examples
  • Nagel-Schreckenberg traffic model
  • Schelling model for segregation
  • 1d diffusion
  • ecological competitions

Conway’s Game of Life

Consider cells on a two-dimensional regular grid. Each cell can be either 1 (alive) or 0 (dead). Based on an initial population, new generations are derived from the current state according to the following rules:

• A dead cell is reborn if and only if it has three living neighbors.
• Living cells die if they have less than two living neighbors.
• Living cells with two or three living neighbors stay alive.
• Living cells with more than three living neighbors die due to overpopulation.

Conway’s Game of Life

Example based on random initial state:

Conway’s Game of Life

Result shows complex structures:

• static or moving objects
• oscillations

• Given a initial configuration, will there be a steady state?

Why is that interesting?

• theory: the question whether a configuration may emerge from another configuration is an undecidable problem.
• studying system behavior as a result of simple individual rules
• top down (differential equations) vs. bottom-up (agent-based models)
• Discrete vs. continuous modeling
• self-organization of complex systems

Historic Overview

Stanislaw Ulam (1940s): modeling growth of chrystals on lattice networks

John von Neumann (1940s): work on self-replicating systems

John Horton Conways (1970s): Game of Life

Stephen Wolfram (1983): Fundamental theoretical work

Stephen Wolfram (2002): “A New Kind of Science”

Numerous practical applications evolved at the same time.

Applications

Cellular automata are suitable to model dynamic spatiotemporal processes / systems in:

• physics (e.g. simulation of wave-like spreading)
• biology (e.g. Corona virus propagation)
• social sciences (e.g. segregation of population groups)
• ecology (e.g. spreading of forest fires)
• …

Formal Definition

A cellular automaton is a 4-tuple \((Z, S, N, f)\):

1. the cell space \(Z\) is a discrete space (cells)
2. the state space \(S\) is a state space, i.e. a set of valid states for each cell
3. the neighborhood definition \(N\) is a finite neighborhood
4. \(f\) is a transition function

Cell space \((\boldsymbol{Z}, S , N , f)\)

Space is partitioned into equal geometric objects:

• 1d cells
• 2d squares, triangles, or hexagons
• 3d, or 4d possible but most applications in 1d or 2d.

State space \((Z, \boldsymbol{S}, N , f)\)

At each point in time, the state of a cell is unique. The finite number of possible cell states cells are based on a set \(S\) containing numbers or letters from an alphabet \(A\): \(S = \{s | s \in A\}\)

A function \(C : Z \rightarrow S\) that assigns states to all cells is called configuration. The configuration at the simulation start is called initial configuration, start configuration, or sometimes initial conditions.

Neighborhood Definition (2d) \((Z, S, \boldsymbol{N}, f)\)

• von Neumann: \(N_r(x_0,y_0) = \{(x,y) : |x-x_0| + |y-y_0| \leq r \}\)
• Moore: \(N_r(x_0,y_0) = \{(x,y) : |x-x_0| \leq r \land |y-y_0| \leq r \}\)

Transition function \((Z, S, N, \boldsymbol{f})\)

The state of a cell at time \(t\) depends on

• the state of the cell at time \(t-1\) and
• the state of neighbouring cells at time \(t-1\).

\[f: Q^n \rightarrow Q\]

\(f\) might be

• a mathematical function, well-defined rules, or transition tables
• stochastic or deterministic

Transition function

For the same initial conditions, deterministic automata always lead to the same simulation results. Stochastic automata include randomness in \(f\) and generally lead to different results for the same initial conditions.

Formal definition: Game of Life

A two-dimensional regular grid: \[Z = \{ (i,j) | i,j \in \mathbb{N} \land 0 \leq i < n \land 0 \leq j < m \}\]

Moore neighborhood: \[N_{i,j} = \{(k,l) \in Z : |x-x_0| \leq 1 \land |y-y_0| \leq 1 \}\]

State space (dead or alive): \[S = \{0,1\}\]

Transition function: \[ f_{i,j}(t+1) = \begin{cases} 1 & \textrm{for} ~ \sum_{(k,l) \in N_{i,j}} f_{k,l}(t) = 3 \\ 1 & \textrm{for} ~ \sum_{(k,l) \in N_{i,j}} f_{k,l}(t) = 2 \land f_{i,j}(t) = 1\\ 0 & \textrm{else} \end{cases} \]

Boundary conditions

Formally, cellular automata assume infinite grids but practical simulation requires finite grids. At the grid boundaries / corners, the neighbourhood is different and must be specified.

Update order

In one simulation step, the transition function is applied to all cells simultaneously (though usually implemented in a sequential for-loop style). To compute the next state of a cell \(z_{i,j}(t+1)\) we only use neighbours and the actual cell at time \(t\). This is called synchronous updating. In contrast, asynchronous updating also uses neighbours at time \(t+1\) if they have been already computed.

Synchronous updating: order of processing cells is NOT important.

Asynchronous updating: order of processing cells is influences results. All examples in this lecture are synchronous.

Classification (Wolfram)

Wolfram distinguishes four different classes of (one-dimensional) CAs based on evolving patterns:

1. Initial configurations evolve into a homogeneous configuration, patterns disappear.
2. Initial configurations evolve into stable oscilating patterns
3. Initial configurations evolve into chaotic structures
4. Initial configurations evolve into complex local structures

Classification (Wolfram)

Examples (1d, \(t\) is on the y-axis -> each new line is a new time step)

(source: http://www.uni-forst.gwdg.de/~wkurth/fs08_v05.pdf)

1. homogeneous state

2. stable / oscilating

Classification (Wolfram)

Examples (1d, \(t\) is on the y-axis -> each new line is a new time step)

(source: http://www.uni-forst.gwdg.de/~wkurth/fs08_v05.pdf)

3. Chaotic development

4. Complex structures

Example 1: Nagel-Schreckenberg traffic model

Modeling traffic:

• Road (single-lane, 1d, circular) is divided into cells. Each cell is either empty or holds a single car.

• Velocity of cars is an integer between 0 and 5.

• Update rules:

  1. Cars with velocity < 5 increase by 1.
  2. Cars with distance less than its current velocity to another car in front slow down to the number of empty cells.
  3. Random lingering: decrease speed of some cars by one with a given probability.
  4. Move cars according their speed

Example 1: Nagel-Schreckenberg traffic model

Example 1: Nagel-Schreckenberg traffic model

Based on varying input parameters (lingering probability, maximum speed), it can be seen that traffic flow depending on traffic density has different optima. This model explains traffic jams as a result of overreactions and not complying with safety gaps.

Extensions:

• multiple lanes
• cars have different maximum speeds
• velocity dependent randomization (VDR)

Example 2: Schelling-model

Schelling (1971) presented a simple CA to explain social segregation:

• CA e.g. represents a city
• Two distinct groups live in the city, at most one agent in a cell.
• Cells might be uninhabitated.
• Agents only accept a limited number of neighbours of the other group. If this number is exceeded, agents move to a different cell which fulfills their requirements.

Example 2: Schelling-model

Parameters:

• Tolerance of both groups (might be different)
• Size of the automaton
• initial conditions

Algorithm update:

1. Find all “unhappy” agents with too many neighbors of the other group
2. Identify target cells for both groups where agents can move
3. Randomly assign target cells to “unhappy” agents
4. If there are not enough target cells, some unhappy agents may not move.

Example: Schelling-model

Example 3: 1d diffusion

Instead of continous diffusion models through partial differential equations, one can look at diffusion at the partcile level and use a one-dimensional CA:

• Regular one-dimensional grid with \(n\) cells
• State space is \(\{0,1\}\)
• Periodic boundaries (conservation of energy)
• Transition function:
  • Particles want to move to the left or right (stochastic rule)
  • Movement is possible only to empty cells (\(0\)) where no other particle wants to move to as well

Example 3: 1d diffusion

Example 4: Plant competition

We consider 5 genera of grasses (Lolium, Agrostis, Holcus, Poa, Cynosurus). Certain genera might displace others over time. We can model this competition as a two-dimensional stochastic CA with a von Neumann neighborhood (4 NBs):

• A cell represents soil which may be vegetated by one of the grass genera.
• The transition function uses a replacement table \(T\) with probabilities that one genus is replaced by another:

Example 4: Plant competition

\(T\) is not symmetric, rows represent neighbours whereas columns represent a certain cell that may or may not be replaced.

Let \(z_{i,j}(t)\) denote a cell and let \(T(s,n)\) be a function that returns column \(s\) and row \(n\) of the replacement table \(T\). To derive the next state of a cell we perform the following operations:

1. Obtain genus of neighbors and plug them in \(T\):

\[ p = \frac{1}{4} \begin{pmatrix} T(z_{i,j}(t), z_{i-1,j}(t)) \\ T(z_{i,j}(t), z_{i,j-1}(t)) \\ T(z_{i,j}(t), z_{i+1,j}(t)) \\ T(z_{i,j}(t), z_{i,j+1}(t)) \end{pmatrix} \]

\(p_k\) is the probability that a cell is replalced by the \(k\)-th neighbor.

Example 4: Plant competition

2. Draw a random number \(r \sim U(0,1)\) and create four nonintersecting intervals \((0,p_1],(p_1,p_1+p_2],(p_1+p_2,p_1+p_2+p_3],(p_1+p_2+p_3,p_1+p_2+p_3+4]\).

3. If \(r\) falls into one of these intervals, \(z_{i,j}(t)\) is replaced by the corresponding neighbor, otherwise it is not replaced.

Example: Cell \(z_{i,j}(t)\) is Agrostis, neighbors are (Holcus,Agrostis, Holcus, Lolium). The replacement table yields \[p = \frac{1}{4}(0.08, 1, 0.08, 0.06)^T = (0.02, 0.25, 0.02, 0.015)^T\] and the intervals are thus \((0,0.02], (0.02, 0.27], (0.27, 0.29], (0.29, 0.305]\).

Assuming e.g. \(r=0.28\), the cell would be replaced by Holcus.

Example 4: Plant competition

The replacement table may come from lab experiments or empirical field studies.

Example 4: Plant competition

Simulation results show that the Agrostis genus “wins”.

More Examples and Software

The (free) NetLogo software (https://ccl.northwestern.edu/netlogo) contains numerous cellular automata as well as many other agent-based models.